Learning to blend rankings a monotonic transformation to blend rankings from heterogeneous domains.

Language pyramid and multi%2Dscale text analysis.

Ranking with query%2Ddependent loss for web search.
Queries describe the users ’ search intent and therefore they play an essential role in the context of ranking for information retrieval and Web search. However, most of existing approaches for ranking do not explicitly take into consideration the fact that queries vary significantly along several dimensions and entail different treatments regarding the ranking models. In this paper, we propose to incorporate query difference into ranking by introducing querydependent loss functions. In the context of Web search, query difference is usually represented as different query categories; and, queries are usually classified according to search intent such as navigational, informational and transactional queries. Based on the observation that such kind of query categorization has high correlation with the user’s differentexpectationontheresult accuracy on different rank positions, we develop position-sensitive query-dependent loss functions exploring such kind of query categorization. Beyond the simple learning method that builds ranking functions with pre-defined query categorization, we further propose a new method that learns both ranking functions and query categorization simultaneously. We apply the querydependent loss functions to two particular ranking algorithms, RankNet and ListMLE. Experimental results demonstrate that query-dependent loss functions can be exploited to significantly improve the accuracy of learned ranking functions. We also show that the ranking function jointly learned with query categorization can achieve better performance than that learned with pre-defined query categorization. Finally, we provide analysis and conduct additional experiments to gain deeper understanding on the advantages of ranking with query-dependent loss functions over other querydependent ranking approaches and query-independent approaches.
Ranking specialization for web search a divide%2Dand%2Dconquer approach by using topical RankSVM.

Time is of the essence improving recency ranking using Twitter data.

Learning distance metric for regression by semidefinite programming with application to human age estimation.

Multi%2Dtask learning for learning to rank in web search.

Smoothing DCG for learning to rank a novel approach using smoothed hinge functions.

Variational Graph Embedding for Globally and Locally Consistent Feature Extraction.
Abstract. Existing feature extraction methods explore either global statistical or local geometric information underlying the data. In this paper, we propose a general framework to learn features that account for both types of information based on variational optimization of nonparametric learning criteria. Using mutual information and Bayes error rate as example criteria, we show that high-quality features can be learned from a variational graph embedding procedure, which is solved through an iterative EM-style algorithm where the E-Step learns a variational affinity graph and the M-Step in turn embeds this graph by spectral analysis. The resulting feature learner has several appealing properties such as maximum discrimination, maximum-relevanceminimum-redundancy and locality-preserving. Experiments on benchmark face recognition data sets confirm the effectiveness of our proposed algorithms. 1
Variational Graph Embedding for Globally and Locally Consistent Feature Extraction.
Abstract. Existing feature extraction methods explore either global statistical or local geometric information underlying the data. In this paper, we propose a general framework to learn features that account for both types of information based on variational optimization of nonparametric learning criteria. Using mutual information and Bayes error rate as example criteria, we show that high-quality features can be learned from a variational graph embedding procedure, which is solved through an iterative EM-style algorithm where the E-Step learns a variational affinity graph and the M-Step in turn embeds this graph by spectral analysis. The resulting feature learner has several appealing properties such as maximum discrimination, maximum-relevanceminimum-redundancy and locality-preserving. Experiments on benchmark face recognition data sets confirm the effectiveness of our proposed algorithms. 1
Interpolating fine texturess with fields of experts prior.

Metric Learning for Regression Problems and Human Age Estimation.

Global ranking by exploiting user clicks.
It is now widely recognized that user interactions with search results can provide substantial relevance information on the documents displayed in the search results. In this paper, we focus on extracting relevance information from one source of user interactions, i.e., user click data, which records the sequence of documents being clicked and not clicked in the result set during a user search session. We formulate the problem as a global ranking problem, emphasizing the importance of the sequential nature of user clicks, with the goal to predict the relevance labels of all the documents in a search session. This is distinct from conventional learning to rank methods that usually design a ranking model defined on a single document; in contrast, in our model the relational information among the documents as manifested by an aggregation of user clicks is exploited to rank all the documents jointly. In particular, we adapt several sequential supervised learning algorithms, including the conditional random field (CRF), the sliding window method and the recurrent sliding window method, to the global ranking problem. Experiments on the click data collected from a commercial search engine demonstrate that our methods can outperform the baseline models for search results re-ranking.
Web%2Dscale classification with naive bayes.
Traditional Naive Bayes Classifier performs miserably on web-scale taxonomies. In this paper, we investigate the reasons behind such bad performance. We discover that the low performance are not completely caused by the intrinsic limitations of Naive Bayes, but mainly comes from two largely ignored problems: contradiction pair problem and discriminative evidence cancelation problem. We propose modifications that can alleviate the two problems while preserving the advantages of Naive Bayes. The experimental results show our modified Naive Bayes can significantly improve the performance on real web-scale taxonomies.
Learning to recognize reliable users and content in social media with coupled mutual reinforcement.
Community Question Answering (CQA) has emerged as a popular forum for users to pose questions for other users to answer. Over the last few years, CQA portals such as Naver and Yahoo! Answers have exploded in popularity, and now provide a viable alternative to general purpose Web search. At the same time, the answers to past questions submitted in CQA sites comprise a valuable knowledge repository which could be a gold mine for information retrieval and automatic question answering. Unfortunately, the quality of the submitted questions and answers varies widely- increasingly so that a large fraction of the content is not usable for answering queries. Previous approaches for retrieving relevant and high quality content have been proposed, but they require large amounts of manually labeled data – which
Enhancing diversity
This report discusses the practices which have been used or recommended for increasing the degree of diversity between redundant implementations of software or software-based systems. Its purpose is to give useful indications for designers, project managers and safety/reliability assessors in deciding about how great an advantage should be expected from the use of these practices, in absolute and in comparative terms. Existing knowledge does not allow one to state any strong general recommendations, but it is possible to improve on the intuitive justifications usually given for these various practices. This report clarifies the ways the various practices are conjectured to aid system reliability, the factors that should affect their efficacy, and thus, for a practitioner, the aspects of a specific project situation that need to be considered to inform decisions. Thus this report
The Social Future of Web Search Modeling
Social, or collaboratively generated content (CGC) is transforming how we seek and find information online: it is now a prominent part of the web information ecosystem, and a powerful platform for information seeking. The resulting archives of both the content and the context of the interactions contain valuable information that is often not available elsewhere, and can be helpful for the development of novel ranking algorithms, and natural language processing, text mining, and information retrieval techniques. We review machine learning techniques for modeling CGC, focusing on tasks such as learning to estimate content quality, relevance, and searcher intent and satisfaction with the retrieved results. We describe how this information can be incorporated into learning-based ranking methods for searching social media, and how CGC could be used to improve performance on key text mining and search tasks. 1
Spectral methods for semi%2Dsupervised manifold learning.
Given a finite number of data points sampled from a low-dimensional manifold embedded in a high dimensional space together with the parameter vectors for a subset of the data points, we need to determine the parameter vectors for the rest of the data points. This problem is known as semi-supervised manifold learning, and in this paper we propose methods to handle this problem by solving certain eigenvalue-problems. Our proposed methods address two key issues in semi-supervised manifold learning: 1) fitting of the local affine geometric structures, and 2) preserving the global manifold structures embodied in the overlapping neighborhoods around each data points. We augment the alignment matrix of local tangent space alignment (LTSA) with the orthogonal projection based on the known parameter vectors, giving rise to the eigenvalue problem that characterizes the semi-supervised manifold learning problem. We also discuss the roles of different types of neighborhoods and their influence on the learning process. We illustrate the performance of the proposed methods using both synthetic data sets as well as data sets arising from applications in video annotations. 1.
Learning object classes from image thumbnails through deep neural networks.

Adapting ranking functions to user preference.
Abstract — Learning to rank has become a popular method for web search ranking. Traditionally, expert-judged examples are the major training resource for machine learned web ranking, which is expensive to get for training a satisfactory ranking function. The demands for generating specific web search ranking functions tailored for different domains, such as ranking functions for different regions, have aggravated this problem. Recently, a few methods have been proposed to extract training examples from user clickthrough log. Due to the low cost of getting user preference data, it is attractive to combine these examples in training ranking functions. However, because of the different natures of the two types of data, they may have different influences on ranking function. Therefore, it is challenging to develop methods for effectively combining them in training ranking functions. In this paper, we address the problem of adapting an existing ranking function to user preference data, and develop a framework for conveniently tuning the contribution of the user preference data in the tuned ranking function. Experimental results show that with our framework it is convenient to generate a batch of adapted ranking functions and to select functions with different tradeoffs between the base function and the user preference data. I.
Convergence and Rate of Convergence of a Manifold%2DBased Dimension Reduction Algorithm.
We study the convergence and the rate of convergence of a particular manifoldbased learning algorithm: LTSA [12]. The main technical tool is the perturbation analysis on the linear invariant subspace that corresponds to the solution of LTSA. We derive the upper bound for errors under the worst case for LTSA; it naturally leads to a convergence result. We then derive the rate of convergence for LTSA in a special case. 1
Learning to rank with ties.

A scalable assistant librarian hierarchical subject classification of books.

Consistent computation of first%2D and second%2Dorder differential quantities for surface meshes.
Differential quantities, including normals, curvatures, principal directions, and associated matrices, play a fundamental role in geometric processing and physics-based modeling. Computing these differential quantities consistently on surface meshes is important and challenging, and some existing methods often produce inconsistent results and require ad hoc fixes. In this paper, we show that the computation of the gradient and Hessian of a height function provides the foundation for consistently computing the differential quantities. We derive simple, explicit formulas for the transformations between the first- and second-order differential quantities (i.e., normal vector and principal curvature tensor) of a smooth surface and the first- and second-order derivatives (i.e., gradient and Hessian) of its corresponding height function. We then investigate a general, flexible numerical framework to estimate the derivatives of the height function based on local polynomial fittings formulated as weighted least squares approximations. We also propose an iterative fitting scheme to improve accuracy. This framework generalizes polynomial fitting and addresses some of its accuracy and stability issues, as demonstrated by our theoretical analysis as well as experimental results.
Learning multiple graphs for document recommendations.
The Web offers rich relational data with different semantics. In this paper, we address the problem of document recommendation in a digital library, where the documents in question are networked by citations and are associated with other entities by various relations. Due to the sparsity of a single graph and noise in graph construction, we propose a new method for combining multiple graphs to measure document similarities, where different factorization strategies are used based on the nature of different graphs. In particular, the new method seeks a single low-dimensional embedding of documents that captures their relative similarities in a latent space. Based on the obtained embedding, a new recommendation framework is developed using semisupervised learning on graphs. In addition, we address the scalability issue and propose an incremental algorithm. The new incremental method significantly improves the efficiency by calculating the embedding for new incoming documents only. The new batch and incremental methods are evaluated on two real world datasets prepared from CiteSeer. Experiments demonstrate significant quality improvement for our batch method and significant efficiency improvement with tolerable quality loss for our incremental method.
Finding the right facts in the crowd factoid question answering over social media.

Exploring social annotations for information retrieval.

Distance Preserving Dimension Reduction Using the QR Factorization or the Cholesky Factorization.

A Comparison of Unsupervised Dimension Reduction Algorithms for Classification.

Co%2Dranking Authors and Documents in a Heterogeneous Network.
The problem of evaluating scientific publications and their authors is important, and as such has attracted increasing attention. Recent graph-theoretic ranking approaches have demonstrated remarkable successes, but most of their applications are limited to homogeneous networks such as the network of citations between publications. This paper proposes a novel method for co-ranking authors and their publications using several networks: the social network connecting the authors, the citation network connecting the publications, as well as the authorship network that ties the previous two together. The new coranking framework is based on coupling two random walks, that separately rank authors and documents following the PageRank paradigm. As a result, improved rankings of documents and their authors depend on each other in a mutually reinforcing way, thus taking advantage of the additional information implicit in the heterogeneous network of authors and documents. The proposed ranking approach has been tested using data collected from CiteSeer, and demonstrates a great improvement in author ranking quality compared with ranking by the number of publications, the number of citations and the PageRank calculated in the authors’ social network.
Discovering Temporal Communities from Social Network Documents.
Discovering communities from documents involved in social discourse is an important topic in social network analysis, enabling greater understanding of the relationships among actors within a social network as well as topical trends in communication. This paper studies the discovery of communities from communication documents produced over time, including the discovery of temporal trends in community memberships. We first formulate static community discovery at a single time period as a tripartite graph partitioning problem. Then we propose to discover the temporal communities by threading the statically derived communities in different time periods using a new constrained partitioning algorithm, which partitions graphs based on topology as well as prior information regarding vertex membership. We evaluate the proposed approach on synthetic datasets and a real-world dataset prepared from the CiteSeer computer science research corpus. Quantitative evaluation on synthetic data demonstrates an high discovery precision and an improvement over the generalized normalized cut approach. Qualitative evaluation on Cite-Seer data shows the effectiveness of the proposed approach in author community discovery and community summarization in research documents. 1

Learning User Clicks in Web Search.


A General Boosting Method and its Application to Learning Ranking Functions for Web Search.
We present a general boosting method extending functional gradient boosting to optimize complex loss functions that are encountered in many machine learning problems. Our approach is based on optimization of quadratic upper bounds of the loss functions which allows us to present a rigorous convergence analysis of the algorithm. More importantly, this general framework enables us to use a standard regression base learner such as single regression tree for £tting any loss function. We illustrate an application of the proposed method in learning ranking functions for Web search by combining both preference data and labeled data for training. We present experimental results for Web search using data from a commercial search engine that show signi£cant improvements of our proposed methods over some existing methods. 1
IKNN Informative K%2DNearest Neighbor Pattern Classification.

DAG%2Dguided parallel asynchronous variational integrators with super%2Delements.

Conical Dimension as an Intrinsic Dimension Estimator and its Applications.

Distance Preserving Dimension Reduction for Manifold Learning.


Efficient Multiclass Boosting Classification with Active Learning.


A regression framework for learning ranking functions using relative relevance judgments.
Effective ranking functions are an essential part of commercial search engines. We focus on developing a regression framework for learning ranking functions for improving relevance of search engines serving diverse streams of user queries. We explore supervised learning methodology from machine learning, and we distinguish two types of relevance judgments used as the training data: 1) absolute relevance judgments arising from explicit labeling of search results; and 2) relative relevance judgments extracted from user clickthroughs of search results or converted from the absolute relevance judgments. We propose a novel optimization framework emphasizing the use of relative relevance judgments. The main contribution is the development of an algorithm based on regression that can be applied to objective functions involving preference data, i.e., data indicating that a document is more relevant than another with respect to a query. Experimental results are carried out using data sets obtained from a commercial search engine. Our results show significant improvements of our proposed methods over some existing methods.
Machine Learning and Robust Data Mining.

Continuum Isomap for manifold learnings.

Topic evolution and social interactions how authors effect research.
We propose a method for discovering the dependency relationships between the topics of documents shared in social networks using the latent social interactions, attempting to answer the question: given a seemingly new topic, from where does this topic evolve? In particular, we seek to discover the pair-wise probabilistic dependency in topics of documents which associate social actors from a latent social network, where these documents are being shared. By viewing the evolution of topics as a Markov chain, we estimate a Markov transition matrix of topics by leveraging social interactions and topic semantics. Metastable states in a Markov chain are applied to the clustering of topics. Applied to the CiteSeer dataset, a collection of documents in academia, we show the trends of research topics, how research topics are related and which are stable. We also show how certain social actors, authors, impact these topics and propose new ways for evaluating author impact.
Incorporating query difference for learning retrieval functions in world wide web search.

Multi%2Dtask text segmentation and alignment based on weighted mutual information.

Boosting the Feature Space Text Classification for Unstructured Data on the Web.
The issue of seeking efficient and effective methods for classifying unstructured text in large document corpora has received much attention in recent years. Traditional document representation like bag-of-words encodes documents as feature vectors, which usually leads to sparse feature spaces with large dimensionality, thus making it hard to achieve high classification accuracies. This paper addresses the problem of classifying unstructured documents on the Web. A classification approach is proposed that utilizes traditional feature reduction techniques along with a collaborative filtering method for augmenting document feature spaces. The method produces feature spaces with an order of magnitude less features compared with a baseline bag-of-words feature selection method. Experiments on both real-world data and benchmark corpus indicate that our approach improves classification accuracy over the traditional methods for both Support Vector Machines and AdaBoost classifiers.
Boosting the Feature Space Text Classification for Unstructured Data on the Web.
The issue of seeking efficient and effective methods for classifying unstructured text in large document corpora has received much attention in recent years. Traditional document representation like bag-of-words encodes documents as feature vectors, which usually leads to sparse feature spaces with large dimensionality, thus making it hard to achieve high classification accuracies. This paper addresses the problem of classifying unstructured documents on the Web. A classification approach is proposed that utilizes traditional feature reduction techniques along with a collaborative filtering method for augmenting document feature spaces. The method produces feature spaces with an order of magnitude less features compared with a baseline bag-of-words feature selection method. Experiments on both real-world data and benchmark corpus indicate that our approach improves classification accuracy over the traditional methods for both Support Vector Machines and AdaBoost classifiers.
Semi%2Dsupervised nonlinear dimensionality reduction.
The problem of nonlinear dimensionality reduction is considered. We focus on problems where prior information is available, namely, semi-supervised dimensionality reduction. It is shown that basic nonlinear dimensionality reduction algorithms, such as Locally Linear Embedding (LLE), Isometric feature mapping (ISOMAP), and Local Tangent Space Alignment (LTSA), can be modified by taking into account prior information on exact mapping of certain data points. The sensitivity analysis of our algorithms shows that prior information will improve stability of the solution. We also give some insight on what kind of prior information best improves the solution. We demonstrate the usefulness of our algorithm by synthetic and real life examples. 1.
R1%2DPCA rotational invariant L1%2Dnorm principal component analysis for robust subspace factorization.

Incorporating query difference for learning retrieval functions in information retrieval.

Probabilistic models for discovering e%2Dcommunities.
The increasing amount of communication between individuals in e-formats (e.g. email, Instant messaging and the Web) has motivated computational research in social network analysis (SNA). Previous work in SNA has emphasized the social network (SN) topology measured by communication frequencies while ignoring the semantic information in SNs. In this paper, we propose two generative Bayesian models for semantic community discovery in SNs, combining probabilistic modeling with community detection in SNs. To simulate the generative models, an EnF-Gibbs sampling algorithm is proposed to address the efficiency and performance problems of traditional methods. Experimental studies on Enron email corpus show that our approach successfully detects the communities of individuals and in addition provides semantic topic descriptions of these communities.
2nd Special issue on matrix computations and statistics.

Two%2Dway Poisson mixture models for simultaneous document classification and word clustering.

Splice site prediction using support vector machines with a Bayes kernel.

Efficient Block Noise Removal Based on Nonlinear Manifolds.

A new Mallows distance based metric for comparing clusterings.
Despite of the large number of algorithms developed for clustering, the study on comparing clustering results is limited. In this paper, we propose a measure for comparing clustering results to tackle two issues insufficiently addressed or even overlooked by existing methods: (a) taking into account the distance between cluster representatives when assessing the similarity of clustering results; (b) constructing a unified framework for defining a distance based on either hard or soft clustering and ensuring the triangle inequality under the definition. Our measure is derived from a complete and globally optimal matching between clusters in two clustering results. It is shown that the distance is an instance of the Mallows distance—a metric between probability distributions in statistics. As a result, the defined distance inherits desirable properties from the Mallows distance. Experiments show that our clustering distance measure successfully handles cases difficult for other measures. 1.
Towards discovering organizational structure from email corpus.
Email logs people&#039;s communication history which provides valuable information regarding the infrastructure of an organization. In this paper, a two-phase framework is introduced to attack the problem of leadership discovery in an organization based on email communication history among the employees. Two heuristic metrics are proposed for evaluating pair-wise leadership factors among a group of employees. We also address several issues in discovering the organization&#039;s structure through mining leadership graph constructed from the leadership factors. Experimental studies are carried out by applying the framework to Enron email corpus.
A Time%2DSeries Biclustering Algorithm for Revealing Co%2DRegulated Genes.

Name disambiguation in author citations using a K%2Dway spectral clustering method.
An author may have multiple names and multiple authors may share the same name simply due to name abbreviations, identical names, or name misspellings in publications or bibliographies 1. This can produce name ambiguity which can affect the performance of document retrieval, web search, and database integration, and may cause improper attribution of credit. Proposed here is an unsupervised learning approach using K-way spectral clustering that disambiguates authors in citations. The approach utilizes three types of citation attributes: co-author names, paper titles, and publication venue titles 2. The approach is illustrated with 16 name datasets with citations collected from the DBLP database bibliography and author home pages and shows that name disambiguation can be achieved using these citation attributes.
A Domain Decomposition Method for Fast Manifold Learning.

Rule%2Dbased word clustering for document metadata extraction.
Text classification is still an important problem for unlabeled text;
A hierarchical naive Bayes mixture model for name disambiguation in author citations.
Because of name variations, an author may have multiple names and multiple authors may share the same name. Such name ambiguity affects the performance of document retrieval, web search, database integration, and may cause improper attribution to authors. This paper presents a hierarchical naive Bayes mixture model, an unsupervised learning approach, for name disambiguation in author citations. This method partitions a collection of citations1 into clusters, with each cluster containing only citations authored by the same author, thus disambiguating authorship in citations to induce author name identities. Three types of citation features are used: co-author names, paper title words, and journal or proceeding title words. The approach is illustrated with 16 name datasets that are constructed based on the publication lists collected from author homepages and DBLP computer science bibliography.
Local Smoothing for Manifold Learning.
We present a new algorithm, Locally Smooth Manifold Learning (LSML), that learns a warping function from a point on an manifold to its neighbors. Important characteristics of LSML include the ability to recover the structure of the manifold in sparsely populated regions and beyond the support of the provided data. Applications of our proposed technique include embedding with a natural out-of-sample extension and tasks such as tangent distance estimation, frame rate up-conversion, video compression and motion transfer. 1
Spectral Clustering for Robust Motion Segmentation.
In this paper, we propose a robust motion segmentation  method based on the matrix factorization and subspace separation. We,  first, mathematically prove that the shape interaction matrix can be  derived using QR decomposition rather than Singular Value Decomposition  (SVD). Using shape interaction matrix, we solve the motion segmentation  problem using spectral graph clustering technique. We exploit  K-way Min-Max cut clustering method. This method yields a good performance  for noise-free data, but it is sensitive to noise. We combine a  cluster refinement method based on subspace separation to the spectral  graph clustering to deal with noise. The proposed method yields very  good performance for both synthetic and real image sequences.
Support Vector Clustering Combined with Spectral Graph Partitioning.

Two supervised learning approaches for name disambiguation in author citations.
Due to name abbreviations, identical names, name misspellings, and pseudonyms in publications or bibliographies (citations), an author may have multiple names and multiple authors may share the same name. Such name ambiguity affects the performance of document retrieval, web search, database integration, and may cause improper attribution to authors. This paper investigates two supervised learning approaches to disambiguate authors in the citations 1. One approach uses the naive Bayes probability model, a generative model; the other uses Support Vector Machines(SVMs) [39] and the vector space representation of citations, a discriminative model. Both approaches utilize three types of citation attributes: co-author names, the title of the paper, and the title of the journal or proceeding. We illustrate these two approaches on two types of data, one collected from the web, mainly publication lists from homepages, the other collected from the DBLP citation databases.
Adaptive Manifold Learning.
The gaming community has produced an informal classification of games that defines genres such as first-person shooters (FPS), real-time strategy (RTS) games, etc. While these genres are generally accepted, producing a more formal
Linear Contour Learning A Method for Supervised Dimension Reduction.

Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment.

Isometric Embedding and Continuum ISOMAP.
Recently, the Isomap algorithm has been proposed  for learning a nonlinear manifold from  a set of unorganized high-dimensional data  points. It is based on extending the classical  multidimensional scaling method for dimension  reduction. In this paper, we present a  continuous version of Isomap which we call  continuum isomap and show that manifold  learning in the continuous framework is reduced  to an eigenvalue problem of an integral  operator. We also show that the continuum  isomap can perfectly recover the underlying  natural parametrization if the nonlinear manifold  can be isometrically embedded onto an  Euclidean space. Several numerical examples  are given to illustrate the algorithm.
Correlating summarization of multi%2Dsource news with k%2Dway graph bi%2Dclustering.
With the emergence of enormous amount of online news, it is desirable to construct text mining methods that can extract, compare and highlight similarities of them. In this paper, we explore the research issue and methodology of correlated summarization for a pair of news articles. The algorithm aligns the (sub)topics of the two news articles and summarizes their correlation by sentence extraction. A pair of news articles are modelled with a weighted bipartite graph. A mutual reinforcement principle is applied to identify a dense subgraph of the weighted bipartite graph. Sentences corresponding to the subgraph are correlated well in textual content and convey the dominant shared topic of the pair of news articles. As a further enhancement for lengthy articles, a k-way bi-clustering algorithm can first be used to partition the bipartite graph into several clusters, each containing sentences from the two news reports. These clusters correspond to shared subtopics, and the above mutual reinforcement principle can then be applied to extract topic sentences within each subtopic group.
Isometric Embedding and Continuum ISOMAP.
Recently, the Isomap algorithm has been proposed  for learning a nonlinear manifold from  a set of unorganized high-dimensional data  points. It is based on extending the classical  multidimensional scaling method for dimension  reduction. In this paper, we present a  continuous version of Isomap which we call  continuum isomap and show that manifold  learning in the continuous framework is reduced  to an eigenvalue problem of an integral  operator. We also show that the continuum  isomap can perfectly recover the underlying  natural parametrization if the nonlinear manifold  can be isometrically embedded onto an  Euclidean space. Several numerical examples  are given to illustrate the algorithm.
Nonlinear Dimension Reduction via Local Tangent Space Alignment.
We present a new algorithm for manifold learning and nonlinear dimension reduction. Based on a set of unorganized data points sampled with noise from the manifold, the local geometry of the manifold is learned by constructing a local tangent space for each data point, and those tangent subspaces are aligned to give the internal global coordinates of the data points with respect to the underlying manifold. We also present a careful error analysis of our algorithm and show that the reconstruction errors are of second-order accuracy. We illustrate our algorithm using curves and surfaces both in 2D/3D Euclidean spaces and higher dimensional Euclidean spaces, and we also address several theoretical and algorithmic issues for further research and improvements.
Automatic Document Metadata Extraction Using Support Vector Machines.
Automatic metadata generation provides scalability and usability for digital libraries and their collections. Machine learning methods offer robust and adaptable automatic metadata extraction. We describe a Support Vector Machine classification-based method for metadata extraction from header part of research papers and show that it outperforms other machine learning methods on the same task. The method first classifies each line of the header into one or more of 15 classes. An iterative convergence procedure is then used to improve the line classification by using the predicted class labels of its neighbor lines in the previous round. Further metadata extraction is done by seeking the best chunk boundaries of each line. We found that discovery and use of the structural patterns of the data and domain based word clustering can improve the metadata extraction performance. An appropriate feature normalization also greatly improves the classification performance. Our metadata extraction method was originally designed to improve the metadata extraction quality of the digital libraries Citeseer[17] and EbizSearch[24]. We believe it can be generalized to other digital libraries. 1 Introduction and related work Interoperability is crucial to the effective use of Digital
Extracting Shared Topics of Multiple Documents.

Correlating Summarization of A Pair of Multilingual Documents.

PageRank HITS and a Unified Framework for Link Analysis.
Two popular webpage ranking algorithms are HITS and PageRank. HITS emphasizes mutual reinforcement between authority and hub webpages, while PageRank emphasizes hyperlink weight normalization and web surfing based on random walk models. We systematically generalize /combine these concepts into a unified framework. The ranking framework contains a large algorithm space
Domain%2Dindependent text segmentation using anisotropic diffusion and dynamic programming.
This paper presents a novel domain-independent text segmentation method, which identifies the boundaries of topic changes in long text documents and/or text streams. The method consists of three components: As a preprocessing step, we eliminate the document-dependent stop words as well as the generic stop words before the sentence similarity is computed. This step assists in the discrimination of the sentence semantic information. Then the cohesion information of sentences in a document or a text stream is captured with a sentence-distance matrix with each entry corresponding to the similarity between a sentence pair. The distance matrix can be represented with a gray-scale image. Thus, a text segmentation problem is converted into an image segmentation problem. We apply the anisotropic diffusion technique to the image representation of the distance matrix to enhance the semantic cohesion of sentence topical groups as well as sharpen topical boundaries. At last, the dynamic programming technique is adapted to find the optimal topical boundaries and provide a zoom-in and zoom-out mechanism for topics access by segmenting text in variable numbers of sentence topical groups. Our approach involves no domain-specific training, and it can be applied to texts in a variety of domains. The experimental results show that our approach is effective in text segmentation and outperforms several state-of-the-art methods.
Rule%2Dbased word clustering for text classification.
This paper introduces a rule-based, context-dependent word clustering method, with the rules derived from various domain databases and the word text orthographic properties. Besides significant dimensionality reduction, our experiments  show that such rule-based word clustering improves by 8% the overall accuracy of extracting bibliographic fields from references, and by 18.32% on average the class-specific performance on the line classification of document headers.
Multidimensional scaling based sensor positioning algorithms in wireless sensor networks.

Simultaneous Classification and Feature Clustering Using Discriminant Vector Quantization with Applications to Microarray Data Analysis.

Adaptive dimension reduction for clustering high dimensional data.
It is well-known that for high dimensional data clustering, standard algorithms such as EM and the K-means are often trapped in local minimum. Many initialization methods were proposed to tackle this problem , but with only limited success. In this paper we propose a new approach to resolve this problem by repeated dimension reductions such that K-means or EM are performed only in very low dimensions. Cluster membership is utilized as a bridge between the reduced dimensional subspace and the original space, providing flexibility and ease of implementation. Clustering analysis performed on highly overlapped Gaussians, DNA gene expression profiles and internet newsgroups demonstrate the e#ectiveness of the proposed algorithm.
Unsupervised Learning Self%2Daggregation in Scaled Principal Component Space.

Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering.
Anovelmethod forsimultaneo  us keyphrase extraction and generic text summarization is proposed by mod eling text d cuments as weighted und rected and weighted bipartite graphs. Spectral graph clustering algorithms are used for partitioning sentences of the d cuments into topical groups with sentence link priors being exploited to enhance clustering quality. Within each topical group, saliency scores for keyphrases and sentences are generated based on a mutual reinforcement principle. The keyphrases and sentences are then ranked accord ing to their saliency scores and selected for inclusion in the top keyphrase list and summaries of the d ocument. Theid ea of build ing a hierarchy of summaries ford ocuments capturingd i#erent levels of granularity is also brieflyd iscussed . Our method is illustrated using several examples from news articles, news broad cast transcripts and webd ocuments. Categories and Subject Descriptors  H.3.3  ystems]: Information Search and Retrieval ---Clustering ; H.4.m  ystems]: Miscellaneous ---Text  n; G.1.3 [Numerical Analysis ]: Numerical Linear Algebra---Singular value deco mpo siti o ; G.2.2 [Discrete Mathematics]: Graph Theory---  Graph algo thms General Terms  Algorithms, Experimentation, Theory Keywords  text summarization, keyphrase extraction, mutual reinforcement principle, bipartite graph, graph partitioning, singular valued ecomposition Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or...
PageRank%2C HITS and a unified framework for link analysis.
Two popular webpage ranking algorithms are HITS and PageRank. HITS emphasizes mutual reinforcement between authority and hub webpages, while PageRank emphasizes hyperlink weight normalization and web surfing based on random walk models. We systematically generalize /combine these concepts into a unified framework. The ranking framework contains a large algorithm space
Correlating multilingual documents via bipartite graph modeling.

Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment
We present a new algorithm for manifold learning and nonlinear dimension reduction. Based on a set of unorganized data points sampled with noise from the manifold, the local geometry of the manifold is learned by constructing a local tangent space for each data point, and those tangent subspaces are aligned to give the internal global coordinates of the data points with respect to the underlying manifold. We also present a careful error analysis of our algorithm and show that the reconstruction errors are of second-order accuracy. We illustrate our algorithm using curves and surfaces both in 2D/3D Euclidean spaces and higher dimensional Euclidean spaces, and we also address several theoretical and algorithmic issues for further research and improvements.
Preface.
part of a series of studies in support of the California Governor’s Advisory Committee on Education Excellence. i PREFACE i LIST OF FIGURES iv
Web document clustering using hyperlink structures.
With the exponential growth of information on the World Wide Web, there is great demand for developing efficient and effective methods for organizing and retrieving the information available. Document clustering plays an important role in information retrieval and taxonomy management for the World Wide Web and remains an interesting and challenging problem in the field of web computing. In this paper we consider document clustering methods exploring textual information, hyperlink structure and co-citation relations. In particular, we apply the normalized-cut clustering method developed in computer vision to the task of hyperdocument clustering. We also explore some theoretical connections of the normalized-cut method to K-means method. We then experiment with normalized-cut method in the context of clustering query result sets for web search engines.
Bipartite Graph Partitioning and Data Clustering.
Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.
A Min%2Dmax Cut Algorithm for Graph Partitioning and Data Clustering.
An important application of graph partitioning is data clustering using a graph model | the pairwise similarities between all data objects form a weighted graph adjacency matrix that contains all necessary information for clustering. Here we propose a new algorithm for graph partition with an objective function that follows the min-max clustering principle. The relaxed version of the optimization of the min-max cut objective function leads to the Fiedler vector in spectral graph partition. Theoretical analyses of min-max cut indicate that it leads to balanced partitions, and lower bonds are derived. The min-max cut algorithm is tested on newsgroup datasets and is found to outperform other current popular partitioning/clustering methods. The linkagebased re nements in the algorithm further improve the quality of clustering substantially. We also demonstrate that the linearized search order based on linkage di erential is better than that based on the Fiedler vector, providing another e ective partition method.
Automatic Topic Identification Using Webpage Clustering.
Grouping webpages into distinct topics is one way to organize the large amount of retrieved information on the web. In this paper, we report that based on similarity metric which incorporates textual information, hyperlink structure and co-citation relations, an unsupervised clustering method can automatically and effectively identify relevant topics, as shown in experiments on several retrieved sets of webpages. The clustering method is a state-of-art spectral graph partitioning method based on normalized cut criterion first developed for image segmentation.
A spectral method to separate disconnected and nearly%2Ddisconnected web graph components.
Separation of connected components from a graph with disconnected graph components mostly use breadth-first search (BFS) or depth-first search (DFS) graph algorithms. Here we propose a new algebraic method to separate disconnected and nearly-disconnected components. This method is based on spectral graph partitioning, following a key observation that disconnected components will show up, after properly sorted, as step-function like curve in the lowest eigenvectors of the Laplacian matrix of the graph. Following an perturbative analysis framework, we systematically analyzed the graph structures, rst on the disconnected subgraph case, and second on the e ects of adding edges sparsely connecting di erent subgraphs as a perturbation. Several new results are derived, providing insights to spectral methods and related clustering objective function. Examples are given illustrating the concepts and results our methods. Comparing to the standard graph algorithms, this method has the same O(jEj + jV jlog(jV j)) complexity, but is easier to implement (using readily available eigensolvers). Further more the method can easily identify articulation points and bridges on nearly-disconnected graphs. Segmentation of a real example of Web graph for query amazon is given. We found that each disconnected or nearly-disconnected components forms a cluster on a clear topic.
Spectral Relaxation for K%2Dmeans Clustering.
The popular K-means clustering partitions a data set by minimizing a sum-of-squares cost function. A coordinate descend method is then used to find local minima. In this paper we show that the minimization can be reformulated as a trace maximization problem associated with the Gram matrix of the data vectors. Furthermore, we show that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the sum-of-squares cost function.
Bipartite graph partitioning and data clustering
Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.
Large%2DScale SVD and Subspace%2DBased Methods for Information Retrieval.

Indexing Management for Distributed Linear Hash Files.

